Most public key cryptography, including most elliptic curve systems, use modular multiplication on large, possibly multi-precision values, which sometimes have as many as 512-4096 bits. Modular multiplication, particularly for the large public key moduli, is slow. Increasing the speed of modular multiplication is almost synonymous with increasing the speed of public key cryptography. Modular multiplication is more involved than multiple-precision multiplication in that there are two parts: multiplication and modular reduction.
A straight forward way to perform modular multiplication is to multiply two operands to generate a product, and then compute a remainder when the product is divided by a modulus, m. Of course, since division is probably the most complicated and costly of the basic multi-precision operations, a modular reduction step that requires explicitly dividing the product by a modulus to compute a remainder is quite expensive and slow.
Some modular reduction techniques such as Montgomery reduction or Barrett reduction permit modular multiplication without explicitly carrying out a classical modular reduction step. Montgomery reduction, for example, requires a pre-computed modular inverse parameter m−1 mod R to compute T modulo m with respect to R for some suitable choice of R. To date, the full range of efficient techniques for computing a modular inverse has not been fully explored.